package two.chapter_4.c4_1;

import two.chapter_1.c1_3.LinkStack;
import two.chapter_1.c1_3.Stack;

/**
 * 寻找路径
 */
public class DepthFirstPaths implements Paths {
    private boolean[] marked;
    private int [] edgeTo;//从起点到一个顶点的已知路径上的最后一个顶点
    private final int s;//起点
    public DepthFirstPaths(Graph g, int s){
        this.s=s;
        marked=new boolean[g.v()];
        edgeTo=new int[g.v()];
        dfs(g,s);
    }

    private void dfs(Graph g, int v) {
        marked[v]=true;
        for (int w:g.adj(v)){
            if (!marked[w]){
                edgeTo[w]=v;
                dfs(g,w);
            }
        }
    }

    /**
     * 测试是否存在从s到v的路径
     * @param v
     * @return
     */
    public boolean hasPathTo(int v){
        return marked[v];
    }

    /**
     * s到v的路径，如果不存在则返回null
     * @param v
     * @return
     */
    public Iterable<Integer> pathTo(int v){
        if (!hasPathTo(v)) return null;
        Stack<Integer> path=new LinkStack<>();
        for (int x=v;x!=s;x=edgeTo[x]){
            path.push(x);
        }
        path.push(s);
        return path;
    }

}

